#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define randomize() (srand((unsigned) time(NULL)))
#define DIV 2000
#define MAX 5000

int ent_size;

void exchange(int &i, int &j)
{
	int tmp = i;
	i = j;
	j = tmp;
}	

void Input(FILE * f_inp, char * array)
{
	(fgets(array,MAX*4,f_inp));

	fseek(f_inp, 0, SEEK_SET);
}

void Output(int * array)
{
	int cnt;
	FILE *src;
	
	if ( (src = fopen("Insertion_Quick.out", "w+b")) == NULL )
	{
		printf("Insertion_Quick.out open error!\n");
		exit(1);
	}

	for ( cnt = 0 ; cnt < MAX ; cnt++ )
	{
		fprintf(src,"%d ", array[cnt]);
	}

	fclose(src);
}

int Insertion(int *f_array, int start, int end)
{
    	int cnt=start, key, tmp;
     
    	for ( cnt = start+1 ; cnt < (end+1) ; cnt++ )
    	{
        	key = f_array[cnt];
        	tmp = cnt-1;
 
			while ( tmp >= start && f_array[tmp] > key )
			{
				f_array[tmp+1] = f_array[tmp];
				tmp--;
         	}
         	f_array[tmp+1] = key;
     	}
}

int Partition(char *f_array, int start, int end)
{
	randomize();
	int size = end-start+1, pvt, tmp, idx[3], tmp_ins[3];
	int cnt = 0, cnt_i = start - 1, cnt_j;
	if ( (end - start) >= 2 )
	{
        do
		{
			for ( cnt = 0 ; cnt < 3 ; cnt++ )
				idx[cnt] = rand()%(size) + start;
		} while((idx[0] == idx[1]) || (idx[1] == idx[2]) || (idx[0] == idx[2]));
		for ( cnt = 0 ; cnt < 3 ; cnt++ )
			tmp_ins[cnt] = f_array[idx[cnt]];

		Insertion(tmp_ins, 0, 2);
		if (tmp_ins[1] == f_array[idx[0]])
		{
			pvt = tmp_ins[1];
			exchange(f_array[idx[0]], f_array[end]); // put pivot number to the end
		} else if (tmp_ins[1] == f_array[idx[1]])
		{
			pvt = tmp_ins[1];
			exchange(f_array[idx[1]], f_array[end]); // put pivot nunber to the end
		} else 
		{		
			pvt = tmp_ins[1];
			exchange(f_array[idx[2]], f_array[end]); // put pivot number to the end
		}

		for ( cnt_j = start ; cnt_j < size-1+start ; cnt_j++ )
		{
			if ( f_array[cnt_j] < pvt )
			{
				exchange(f_array[++cnt_i], f_array[cnt_j]); // if a number in the array is bigger than pivot, send it to the first
			}
		}
		exchange(f_array[++cnt_i], f_array[end]);
	
		return cnt_i;
	}
	else
		return 0;
}

char * Tokenize(char * string)
{
	char * ptr[2];
	char * tmpStr = (char *)malloc(4*sizeof(char));
	tmpStr = strtok_r(string, " ", &ptr[0]);
	strtok_r(NULL, " ", &ptr[0]);

	return tmpStr;
}

void IQSort(char * f_array, int start, int end)
{
	//char ** parseNum = (char **)calloc(MAX,sizeof(char)*5);
	//memset(parseNum
	char parseNum[MAX][5];
	int cnt;

	//for ( cnt = 0 ; cnt < MAX ; cnt++ )
	//	char * parseNum[cnt] = (char *)calloc(5, sizeof(char));

	for ( cnt = 0 ; cnt < MAX ; cnt++ )
		strcpy(parseNum[cnt], Tokenize(f_array));

	while ( start < end )
	{
		int size = end-start+1;
		if ( size <= ent_size/DIV )
			return;
		else 
		{
			int q = Partition(f_array,start,end);
			int q = 1;
			if ( q == 0 ) break;
			int former = q - start;
			int latter = end - q;
			if ( former < latter )
			{
				IQSort(f_array, start, q-1);
				start = q + 1;
			} else
			{
				IQSort(f_array, q+1, end);
				end = q - 1;
			}
		}
	}

	/*for ( cnt = 0 ; cnt < MAX ; cnt++ )
		free(parseNum[cnt]);
	free(parseNum);
	*/
}

int main()
{
	int cnt, cnt_inp = 0;
	char size[10];
	int i_size;
	FILE *inp;
	time_t Tstart = 0, Tend = 0;
   
	Tstart = clock();
	if ((inp = fopen("Insertion_Quick_1.txt", "rb")) == NULL)
	{
		printf("fopen error!\n");
		exit(1);
	}
		
	//ent_size = atoi(fgets(size,20,inp)); 
	//i_size = ent_size;

	char * array = (char *)calloc(MAX,sizeof(char)*4);

	Input(inp, array);
	
	int start=0, end=MAX-1;

	IQSort(array, start, end);	

	//Insertion(array, start, end);

	//Output(array);

	Tend = clock();

	printf("Time elapsed = %.2lf\n", (double)(Tend-Tstart)/CLOCKS_PER_SEC);

 	return 0;
}
